The present invention relates to a countermeasure method in an electronic component implementing a secret key cryptographic algorithm. They are used in applications where the access to services or data is strictly controlled. They have an architecture formed around a microprocessor and memories, one of which is a program memory which contains the secret key.
These components are notably used in smart cards, for certain applications thereof. These are for example applications for accessing certain data banks, banking applications, or remote payment applications, for example for television, petrol dispensing or passing through motorway tolls.
These components or these cards therefore implement a secret key cryptographic algorithm, the best known of which is the DES (Data Encryption Standard) algorithm. Other secret key algorithms exist, such as the RC5 algorithm or the COMP128 algorithm. This list is of course not exhaustive.
Briefly and in general terms, the function of these algorithms is to calculate an encrypted message from a message applied at the input (to the card) by a host system (server, cash dispenser, etc.) and the secret key contained in the card, and to supply in return to the host system this encrypted message, which allows for example the host system to authenticate the component or the card, to exchange data, etc.
However, it has turned out that these components or these cards are vulnerable to attacks consisting of a differential current consumption analysis and which allow ill-intentioned third parties to find the secret key. These attacks are referred to as DPA (Differential Power Analysis) attacks.
The principle of these DPA attacks is based on the fact that the current consumption of a microprocessor executing instructions varies according to the data manipulated.
Notably, an instruction of a microprocessor manipulating a data bit generates two different current profiles depending on whether this bit has the value xe2x80x9c1xe2x80x9d or xe2x80x9c0xe2x80x9d. Typically, if the instruction is manipulating a xe2x80x9c0xe2x80x9d, there is at that execution instant a first consumed current amplitude, and if the instruction is manipulating a xe2x80x9c1xe2x80x9d, there is a second consumed current amplitude, different from the first.
The characteristics of cryptographic algorithms are known: the calculations performed and parameters used. The sole unknown is the secret key contained in program memory. This cannot be deduced from the sole knowledge of the message applied at the input and the encrypted message supplied in return.
However, in a cryptographic algorithm, certain calculated data depend solely on the message applied in clear at the input of the card and the secret key contained in the card. Other data calculated in the algorithm can also be recalculated solely from the encrypted message (generally supplied in clear at the output of the card to the host system) and the secret key contained in the card. More precisely, each bit of these particular data items can be determined from the input or output message, and from a limited number of particular bits of the key.
Thus, each bit of a particular data item has corresponding thereto a sub-key formed by a particular group of bits of the key.
The bits of these particular data items which can be predicted are referred to in the remainder of the document as target bits.
The basic idea of the DPA attack is thus to use the difference in the current consumption profile of an instruction depending on whether it is manipulating a xe2x80x9c1xe2x80x9d or a xe2x80x9c0xe2x80x9d and the possibility of calculating a target bit by the instructions of the algorithm from a known input or output message and a hypothesis on the corresponding sub-key.
The principle of the DPA attack is therefore to test a given sub-key hypothesis by applying, to a large number of current measurement curves, each relating to an input message known to the attacker, a Boolean selection function, a function of the sub-key hypothesis, and defined for each curve by the value predicted for a target bit.
Making a hypothesis on the sub-key concerned in fact gives the capability of predicting the value xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d which this target bit will take for a given input or output message.
There can then be applied, as a Boolean selection function, the value xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d predicted for the target bit for the considered sub-key hypothesis, in order to sort these curves into two bundles: a first bundle groups together the curves where the target bit was manipulated at xe2x80x9c0xe2x80x9d and a second bundle groups together the curves where the target bit was manipulated at xe2x80x9c1xe2x80x9d according to the sub-key hypothesis. By calculating the current consumption mean in each bundle, a mean consumption curve M0(t) for the first bundle and a mean consumption curve M1(t) for the second bundle are obtained.
If the sub-key hypothesis is correct, the first bundle actually groups together all the curves among the N curves where the target bit was manipulated at xe2x80x9c0xe2x80x9d and the second bundle actually groups together all the curves among the N curves where the target bit was manipulated at xe2x80x9c1xe2x80x9d. The mean consumption curve M0(t) of the first bundle will then have a mean consumption everywhere except at the moments at which the critical instructions are executed, with a current consumption profile characteristic of manipulation of the target bit at xe2x80x9c0xe2x80x9d (profile0). In other words, for all these curves, all the manipulated bits had as many chances of having the value xe2x80x9c0xe2x80x9d as having the value xe2x80x9c1xe2x80x9d, except the target bit which always had the value xe2x80x9c0xe2x80x9d. This can be written:
M0(t)=[(profile0+profile1)/2]txe2x89xa0tci+[profile0]tci
that is
M0(t)=[Vmt]txe2x89xa0tci+[profile0]tci
where tci represents the critical instants, at which a critical instruction was executed.
Similarly, the mean consumption curve M1(t) of the second bundle corresponds to a mean consumption everywhere except at the moments at which the critical instructions are executed, with a current consumption profile characteristic of manipulation of the target bit at xe2x80x9c1xe2x80x9d (profile1). The following can be written:
M1(t)=[(profile0+profile1)/2]txe2x89xa0tci+[profile1]tci
that is
M1(t)=[Vmt]txe2x89xa0tci+[profile1]tci
It has been seen that the two profiles profile0 and profile1 are not equal. The difference in the curves M0(t) and M1(t) then gives a signal DPA(t), the amplitude of which is equal to profile0xe2x88x92profile1 at the critical instants tci at which the critical instructions manipulating this bit are executed, that is to say, in the example depicted in FIG. 1, at the locations tc0 to tc6, and the amplitude of which is approximately equal to zero apart from the critical instants.
If the sub-key hypothesis is false, the sort does not correspond to reality. Statistically, there are then, in each bundle, as many curves where the target bit was actually manipulated at xe2x80x9c0xe2x80x9d as curves where the target bit was manipulated at xe2x80x9c1xe2x80x9d. The resultant mean curve M0(t) is then situated around a mean value given by (profile0+profile1)/2=Vm, since, for each of the curves, all the bits manipulated, including the target bit, have as many chances of having the value xe2x80x9c0xe2x80x9d as having the value xe2x80x9c1xe2x80x9d.
The same reasoning on the second bundle leads to a mean current consumption curve M1(t), the amplitude of which is situated around a mean value given by (profile0+profile1)/2=Vm.
The signal DPA(t) supplied by the difference M0(t)xe2x88x92M1(t) is in this case substantially equal to zero. The signal DPA(t) in the case of a false sub-key hypothesis is depicted in FIG. 2.
Thus, the DPA attack exploits the difference in the current consumption profile during execution of an instruction according to the value of the manipulated bit, in order to carry out a current consumption curve sort according to a Boolean selection function for a given sub-key hypothesis. By carrying out a differential analysis of the mean current consumption between the two bundles of curves obtained, an information signal DPA(t) is obtained.
Overall, the steps in a DPA attack then consist in:
axe2x80x94taking N random messages (for example N equal to 1000);
bxe2x80x94making the card execute the algorithm for each of the N random messages, plotting the current consumption curve each time (measured on the power supply terminal of the component);
cxe2x80x94making a hypothesis on a sub-key; FIG. 2). It is necessary to return to step cxe2x80x94and make a new hypothesis on the sub-key.
If the hypothesis proves to be correct, the procedure can move to the evaluation of other sub-keys, until the key has been reconstructed as much as possible. For example, with a DES algorithm, use is made of a key of 64 bits, only 56 of which are useful. With a DPA attack, it is possible to reconstruct at least 48 bits of the 56 useful bits.
Two documents relating to the technological background are cited below. These are the documents NAKAO Y ET AL: xe2x80x9cTHE SECURITY OF AN RDES CRYPTOSYSTEM AGAINST LINEAR CRYPTANALYSISxe2x80x9d, IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS, COMMUNICATIONS AND COMPUTER SCIENCES, JP, INSTITUTE OF ELECTRONICS INFORMATION AND COMM. ENG. TOKYO, vol. E79-A, no. 1, page 12-19 XP000558714 ISSN: 0916-8508, denoted D1 and WO 00 27068, denoted D2.
The document D1 relates to a cryptosystem using the DES in order to be made secure.
The document D2 relates to an electronic component implementing a secret key algorithm; the implementation of this algorithm comprises the use of first means from an input data item (E) in order to supply an output data item.
The aim of the present invention is to implement, in an electronic component, a countermeasure method against attacks by differential analysis which brings about a null signal DPA(t), even where the sub-key hypothesis is correct.
In this way, nothing allows the correct sub-key hypothesis case to be distinguished from the false sub-key hypothesis cases. By means of this countermeasure, the electronic component is guarded against DPA attacks.
It is known through the French patent application FR 2 785 477 published on 5 May 2000, by the GEMPLUS company, the content of which in its entirety forms an integral part of the present application, that it is not sufficient to arrange that the signal DPA(t) is null in relation to a given target bit.
This is because, if the value taken by a number of target bits of the same data item manipulated by the critical instructions is considered, the curves will have to be sorted, no longer into two bundles, but into a number of bundles. It is no longer a binary selection function. It can be shown that, by next grouping together these bundles in one way or another, a signal DPA(t) can be obtained which is non-null in the case of a correct sub-key hypothesis, whereas it would have been null if a sort had been performed according to a binary selection function on a single target bit.
Let, for example, two target bits of the same data item be taken. These two target bits can take the following 22 values: xe2x80x9c00xe2x80x9d, xe2x80x9c01xe2x80x9d, xe2x80x9c10xe2x80x9d and xe2x80x9c11xe2x80x9d.
By applying the selection function to the N=1000 measured current consumption curves, four bundles of curves are obtained. If the sort is correct, a first bundle of around 250 curves corresponds to the value xe2x80x9c00xe2x80x9d, a second bundle of around 250 curves corresponds to the value xe2x80x9c01xe2x80x9d, a third bundle of around 250 curves corresponds to the value xe2x80x9c10xe2x80x9d and a fourth bundle of around 250 curves corresponds to the value xe2x80x9c11xe2x80x9d.
If the first and fourth bundles are grouped together in a first group and the second and third bundles are grouped together in a second group, two groups which are not equivalent are obtained.
In the first group, the two bits have as many chances of having the value xe2x80x9c00xe2x80x9d as having the value xe2x80x9c11xe2x80x9d. The mean value at the critical instants of all the consumption curves in this group can be written:
M1(tci)=[consumption(xe2x80x9c00xe2x80x9d)+consumption(xe2x80x9c11xe2x80x9d)]/2
In the second group, the two bits have as many chances of having the value xe2x80x9c01xe2x80x9d as having the value xe2x80x9c10xe2x80x9d. The mean value at the critical instants of all the consumption curves in this group can be written:
M2(tci)=[consumption(xe2x80x9c01xe2x80x9d)+consumption(xe2x80x9c10xe2x80x9d)]/2
If the difference between these two means is calculated, a non-null signal DPA(t) is obtained. In other words, the two groups whose mean consumptions are being compared do not have an equivalent content.
In the aforementioned French patent application, an attempt has been made to prevent any significant signal in the DPA attack sense being obtained. Whatever the number of target bits taken, whatever the combination of bundles made for comparing the mean consumptions, the signal DPA(t) will always be null. For this, it is necessary to obtain equivalent bundles, whatever the number of target bits considered.
The aforementioned French patent application, as a solution to these various technical problems, proposes the use of a random value in an EXCLUSIVE OR operation with at least some output data from calculation means used in the algorithm.
With the use of such a random value, the data manipulated by the critical instructions become unpredictable while having a correct result at the output of the algorithm.
In the invention, however, it was ascertained that attacks could still be carried out successfully at well-determined locations in the algorithm execution, notably at the input and output of the algorithm.
The object of the present invention is a countermeasure method in which these attacks are also made impossible. According to the invention, a second random value is used, applied to the input parameters of the cryptographic algorithm, in an EXCLUSIVE OR operation. This second random value propagates through the whole algorithm, so that the data which were not protected by the first random value are protected by the second.
Thus, according to the invention, depending on the location in the algorithm, the data are protected either by the first random value, or by the second, or by a combination of these two random values.
As characterised, the invention therefore relates to a countermeasure method in an electronic component implementing a secret key cryptographic algorithm, the implementation of which comprises a number of successive calculation cycles in order to supply, from first input data applied to the first cycle, final data at the output of the last cycle allowing the production of an encrypted message, each calculation cycle using calculation means for supplying an output data item from an input data item, said calculation means comprising the application of a first random value (u) in order to obtain at the output an unpredictable data item, characterised in that the method comprises the use of means of applying a second random value to said first input data, according to an EXCLUSIVE OR operation.